package com.lw.leetcode.back.b;

/**
 * back
 * 1079. 活字印刷
 *
 * @Author liw
 * @Date 2021/8/7 16:04
 * @Version 1.0
 */
public class NumTilePossibilities {

    public static void main(String[] args) {
        NumTilePossibilities test = new NumTilePossibilities();
        String str = "AAABBC";
        int i = test.numTilePossibilities(str);
        System.out.println(i);
    }

    /**
     * 1：统计length 个字符可排列组合而成的字符串，可用 n =  1 * 2 * 3 * ... * (length - 1) * length 。
     * 2：若是其中有重复的字符，需要除去重复的字符串，
     * m = 1 * 2 * 3 * ... * (c - 1) * c (c个重复的某字符串) * [同理，每个重复的字符串的个数都如此计算。]
     * 例如 AAABBC 6 * 5 * 4 * 3 * 2 * 1 / （1 * 2 * 3 * 1 * 2） = 60 个
     * 3：递归遍历，每个字符减少一个以后，所组成的字符，最后相加，即为所求。
     * 4：因为字符都是大写，可用数组来记录其出现的次数。
     */

    int sum = 0;

    public int numTilePossibilities(String tiles) {

        int length = tiles.length();
        int[] arr = new int[26];
        for (int i = 0; i < length; i++) {
            arr[tiles.charAt(i) - 'A']++;
        }
        find(arr, length, 0);
        return sum;
    }

    private void find(int[] arr, int n, int index) {
        if (n == 1) {
            sum++;
            return;
        }
        if (n > 0) {
            int a = 1;
            int b = 1;
            for (int i = 2; i <= n; i++) {
                a *= i;
            }
            for (int value : arr) {
                if (value > 1) {
                    for (int i = 2; i <= value; i++) {
                        b *= i;
                    }
                }
            }
            sum += (a / b);
            for (int i = index; i < 26; i++) {
                int value = arr[i];
                if (value > 0) {
                    arr[i]--;
                    find(arr, n - 1, i);
                    arr[i]++;
                }
            }
        }
    }

}
